package fun.coding.topcoder.singleround;

import java.util.HashMap;

public class TrafficCongestionDivTwo {

    public long theMinCars(int treeHeight) {
        HashMap<Integer, Long> cache = new HashMap<Integer, Long>();
        cache.put(1, 1L);
        cache.put(2, 3L);
        
        return theMinCarsHelper(treeHeight, cache);
    }
    // Note here the tree height is defined as the number of leaves between root and leaf.
    // T(N) = 1 + (1 + T(1) + T(2) + T(N-2)) * 2
    private long theMinCarsHelper(int treeHeight, HashMap<Integer, Long> cache) {
        //if (treeHeight == 1) return 1;
        //if (treeHeight == 2) return 3;
        if (cache.containsKey(treeHeight)) return cache.get(treeHeight);
        
        long res = 0;
        
        for (int i = 1; i <= treeHeight - 2; ++i) {
            res += theMinCarsHelper(i, cache);
        }
        
        res++;
        res = 2 * res;
        res++;
        
        if (!cache.containsKey(treeHeight)) {
            cache.put(treeHeight, res);
        }
        
        return res;
    }
}
